// https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> ans(2);
        int n = numbers.size();

        for (int i = 0; i < n; i++) {
            int num = target - numbers[i];
            ans[0] = i + 1;
            
            int left = i + 1, right = n - 1;
            while (left <= right) {
                int mid = (right - left) / 2 + left;

                if (numbers[mid] == num) {
                    ans[1] = mid + 1;
                    return ans;
                } else if (numbers[mid] > num)  {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        ans[0] = -1;
        ans[1] = -1;
        return ans;
    }
};